package Tree.Recursive;

import Utils.TreeNode;

/**
 * 最长同值路径: 给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。
 * 这条路径可以经过也可以不经过根节点。
 * 令 arrow_length(node) 为从节点 node 延伸出的最长箭头的长度。如果 node.Left 存在且与节点 node 具有相同的值，则该值就会是 1 + arrow_length(node.left)。在 node.right 存在的情况下也是一样。
 * 当我们计算箭头长度时，候选答案将是该节点在两个方向上的箭头之和。我们将这些候选答案记录下来，并返回最佳答案。
 * Lettcode 687: https://leetcode-cn.com/problems/longest-univalue-path/
 * 吐槽： 这题是简单题？
 */
public class longestUnivaluePath {
    int res = 0;

    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return res;
    }

    /**
     * 用于求解以变量root为根节点的最长同值路径。 只返回单条边的结果
     * 注意，该函数不考虑全局最大值，每一次求解得到的都是包含该节点的局部最优值
     * @param root 树的节点
     * @return 从root节点出发的最长同值路径的长度
     */
    private int dfs(TreeNode root) {
        // 递归终止条件
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;
        int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
        // 返回全局最大值
        res = Math.max(res, leftPath + rightPath);
        // 返回以变量root为根节点的最长同值路径
        return Math.max(leftPath, rightPath);
    }
}
